void quickSort(int *arr, int left, int right) {
    int mid = (left + right) / 2;
    if (left < right) {
        if (arr[left] > arr[right]) {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }
        if (arr[mid] > arr[right]) {
            int tmp = arr[mid];
            arr[mid] = arr[right];
            arr[right] = tmp;
        }
        if (arr[left] > arr[mid]) {
            int tmp = arr[left];
            arr[left] = arr[mid];
            arr[mid] = tmp;
        }
        int i = left;
        int j = right;
        int pivot = arr[mid];

        while(i <= j) {
            while(arr[i] < pivot) i++;
            while(arr[j] > pivot) j--;
            if (i <= j) {
                int tmp = arr[i];
                arr[i++] = arr[j];
                arr[j--] = tmp;
            }
        }
        if (left < j) quickSort(arr, left, j);
        if (i < right) quickSort(arr, i, right);
    }
    return;
}*